牛客 101
> Last Format Time:7/9/2026 23:46:20
区间删除
#哈希表 小红拿到了一个数组,她准备进行最多一次以下操作:
选择两个相等的元素,将这两个元素之间的所有元素删除。
小红想知道,她最多可以删除多少个元素?
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void (async function () {
let line;
while ((line = await readline())) {
let count = parseInt(line);
if (isNaN(count)) break;
let arrStr = await readline();
let arr = Array.from(arrStr.split(" ").map(Number));
let res = 0;
let firstPos = new Map(); // 哈希表:记录每个数字第一次出现的下标
for (let i = 0; i < arr.length; i++) {
let num = arr[i];
if (firstPos.has(num)) {
// 如果这个数字之前出现过,计算距离
// 题目要求的距离是中间隔了多少个元素,所以是 j - i - 1
let distance = i - firstPos.get(num) - 1;
res = Math.max(res, distance);
} else {
// 如果是第一次遇到这个数字,记录下它的下标
firstPos.set(num, i);
}
}
console.log(res);
}
})();
最小间距
小红将nn个珠子排成一排,然后将它们串起来,连接成了一串项链(连接后为一个环,即第一个和最后一个珠子也是相邻的),任意相邻两个珠子的距离为1。已知初始共有3个珠子是红色的,其余珠子是白色的。
小红拥有无穷的魔力,她可以对项链上的相邻两个珠子进行交换。小红希望用最小的交换次数,使得任意两个红色的珠子的最小距离不小于kk,你能帮小红求出最小的交换次数吗?
输入例子:
2 6 2 1 2 3 5 2 1 3 4
输出例子:
2 -1
例子说明:
第一组样例,六个珠子为红红红白白白。第一次操作交换第一个和第六个珠子,第二次操作交换第三个和第四个珠子。
第二组询问,一共有5个珠子,其中有3个红珠子,因此无论如何都会有两个红珠子相邻,不可能满足任意两个红珠子的最小距离不小于2。